/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool Find(TreeNode *root, TreeNode *x)
    {
        if(nullptr == root)
            return false;
        
        if(root == x)
            return true;
        else
            return Find(root->left, x) || Find(root->right, x);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 这个判断其实可以省略，因为p和q都在这棵树上，不会存在递归到空树的情况
        if(nullptr == root)
            return nullptr;

        // p 或 q 如果有一个是根，那么他就是公共祖先
        if(p == root || q == root)
            return root;

        // 查找并记录 p 和 q 的位置
        bool pInleft, pInright, qInleft, qInright;
        pInright = Find(root->right, p);
        pInleft = !pInright;

        qInleft = Find(root->left, q);
        qInright = !qInleft;

        // 如果 p 和 q 在根的左右两侧(可能 p在左q在右，也可能 p在右q在左)，这时根就是公共祖先
        if((pInleft && qInright) || (pInright && qInleft))
            return root;

        // 如果在同侧，则递归重复上面的代码
        if(pInleft && qInleft)
            return lowestCommonAncestor(root->left, p, q);
        if(pInright && qInright)
            return lowestCommonAncestor(root->right, p, q);

        return nullptr;
    }
};